package leetcodev1.数组;

public class LeetCode53 {

    //我一直关注的起点和终点
    //看过答案后发现其中和终点并不重要，重要的累加和
    public int maxSubArray(int[] nums) {
        int pre = 0, maxAns = nums[0];
        for (int x : nums) {
            pre = Math.max(pre + x, x);
            maxAns = Math.max(maxAns, pre);
        }
        return maxAns;
    }

    public int maxSubArray1(int[] nums) {
        //异常处理
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int chooseSum = 0, ret = nums[0];
        for (int num : nums) {
            //当前最优累加和
            //不使用当前最优解 使用当前的最优解
            chooseSum = Math.max(num, chooseSum + num);
            ret = Math.max(ret, chooseSum);
        }
        return ret;
    }

    //暴力解
    //超时
    public int maxSubArray2(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int ret = Integer.MIN_VALUE;
        //起始位置
        for (int i = 0; i < nums.length; i++) {
            int sum = 0;
            //终点位置
            for (int j = i; j < nums.length; j++) {
                sum += nums[j];
                ret = Math.max(ret, sum);
            }
        }

        return ret;
    }

    //暴力解，遍历出所有起终点情况
    //对撞指针
    //bug
    public int maxSubArray3(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }

        int ret = sum, i = 0, j = nums.length - 1;
        while (i < j) {
            if (nums[i] < nums[j]) {
                sum -= nums[i++];
            } else {
                sum -= nums[j--];
            }
            ret = Math.max(ret, sum);
        }
        return ret;
    }
}
